package sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
 * 平均 O(n2)
 * 最好 O(n2)
 * 最坏 O(n2)
 * 空间 O(1)
 * 排序方式 In-place
 * 稳定性 不稳定
 */
public class Select {
    private int [] a = {1,6,2,4,1,5,9};

    private void sort(){
        for(int i = 0;i< a.length;i++){
            int min = i;
            for(int j = i; j < a.length; j++){
                if(a[j] < a[min]){
                    min = j;
                }
            }
            int temp;
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }

    private void print(){
        System.out.println(Arrays.toString(a));
    }

    int  getCombinations(String numStr) {
        return f(numStr, numStr.length(), 4);
    }

    boolean b200(String a){
        return Integer.valueOf(a) >= 200;
    }

    int f(String str, int end, int n){
        int count = 0;
        if (n <= 1) return 0;
        if (n  == 1){
            if (b200(str.substring(0, end))) return 0;
            else {
                return 1;
            }
        } else{

            count += f(str, end - 1, n - 1) + 1;
            count += f(str, end - 2, n - 2) + 1;
            if(!b200(str.substring(end - 3, end))){
                count += f(str, end - 3,n - 3);
            }
            return count;
        }
    }
    public static void main(String [] args){
        Select maoPao = new Select();
        System.out.println(maoPao.getCombinations("11111"));
    }
}
